package algo.graph;

import ds.adt.Graph;

public class Cycle {

	private boolean[] marked;
	private boolean hasCycle;

	public Cycle(Graph g) {
		this.marked = new boolean[g.V()];

		for (int i = 0; i < g.V(); i++) {
			if (!marked[i]) {
				dfs(g, i, i);
			}
		}
	}

	/**
	 * Implements DFS. If the graph doesn't contains cycle then while
	 * backtracking the visiting vertex(w) and the parent's parent vertex will
	 * be same otherwise graph has cycle.
	 * 
	 * 
	 * @param g
	 * @param v
	 * @param u
	 */
	private void dfs(Graph g, int v, int u) {
		marked[v] = true;
		for (int w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w, v);
			} else if (w != u) {
				hasCycle = true;
			}
		}
	}

	public boolean hasCycle() {
		return hasCycle;
	}

	public static void main(String[] args) {
		Graph g = new Graph(5);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(2, 0);
		// g.addEdge(0, 3);
		// g.addEdge(0, 4);

		Cycle c = new Cycle(g);
		System.out.println("Graph has cycle ? " + c.hasCycle());
	}

}
